﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;

namespace psieve
{
    public static class Utils
    {
        private static readonly Random random = new Random();

        public static long Product(this IEnumerable<long> list)
        {
            return list.Aggregate((total, next) => total*next);
        }

        public static BigInteger Product(this IEnumerable<BigInteger> list)
        {
            return list.Aggregate((total, next) => total * next);
        }

        // ceil(log2(this < 0 ? -this : this + 1))
        public static int BitLength(this BigInteger n)
        {
            if (n.IsZero)
                return 1;

            byte[] ray = n.ToByteArray();
            byte high = ray[ray.Length - 1];

            int add;
            if(high >= 128)
                add = 8;
            else if (high >= 64)
                add = 7;
            else if (high >= 32)
                add = 6;
            else if (high >= 16)
                add = 5;
            else if (high >= 8)
                add = 4;
            else if (high >= 4)
                add = 3;
            else if (high >= 2)
                add = 2;
            else if (high >= 1)
                add = 1;
            else
                add = 0;

            return (ray.Length - 1) * 8 + add;
        }

        public static BigInteger Sqrt(this BigInteger n, BigInteger lower, BigInteger upper)
        {
            while (upper >= lower)
            {
                BigInteger mid = (lower + upper) >> 1;

                if (mid * mid > n)
                    upper = mid - 1;
                else
                    lower = mid + 1;
            }

            return lower - 1;
        }

        public static BigInteger Sqrt(this BigInteger n)
        {
            int bitLen = n.BitLength();

            return Sqrt(n, n >> (bitLen / 2 + 1), n >> (bitLen / 2 - 1));
        }

        public static bool IsProbablyPrime(this BigInteger n, int k)
        {
            // Miller–Rabin test

            if(n < 1)
                throw new ArgumentException("n < 1: " + n);

            if(n.IsOne)
                return false;

            if(n.ToByteArray()[0] % 2 == 0)
                return false;

            int s = 0;

            BigInteger d = n - 1;
            while (d%2 == 0)
            {
                s++;
                d >>= 1;
            }

            for (int i = 0; i < k; i++)
            {
                BigInteger a;

                do
                {
                    a = GenerateRandomByBits((n - 1).BitLength());
                } while (a < 2 || a > (n - 1));


                BigInteger x = BigInteger.ModPow(a, d, n);
                if(x == 1)
                    continue;

                for (int j = 0; j < s - 1 && x != n-1; j++)
                {
                    x = BigInteger.ModPow(x, 2, n);
                    if(x == 1)
                        return false;
                }

                if (x != n - 1)
                    return false;
            }

            return true;

        }

        public static BigInteger GenerateRandomByBits(int bits)
        {
            if(bits < 1)
                throw new ArgumentException("bits=" + bits);

            byte[] val = new byte[bits / 8 + 1];
            random.NextBytes(val);

            // set high bit to 1
            int b1 = bits - 1;
            val[b1 / 8] |= (byte)(1 << (b1 % 8));

            // set all higher bits to 0
            for (int x = bits; x < val.Length*8; x++)
                val[x/8] &= (byte) ~(1 << (x%8));

            return new BigInteger(val);
        }

        public static BigInteger GenerateRandomByDigits(int digits)
        {
            string s = "" + random.Next(1, 9);

            for (int x = 2; x <= digits; x++)
                s += random.Next(0, 9);

            return BigInteger.Parse(s);
        }

        public static BigInteger GenerateProbablyPrimeByBits(int bits, int k)
        {
            while (true)
            {
                BigInteger a = GenerateRandomByBits(bits);
                if (a.IsProbablyPrime(k))
                    return a;
            }
        }
    }
}
